package code.oldCode.feishuSpecializedTraining.back_trace;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/17
 * @description
 */
public class MyBackTrace4 {
    // 491. 非递减子序列
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        getSubsequences(0, nums, new ArrayList<>(), lists);
        return lists;
    }

    public void getSubsequences(int pos, int[] nums, List<Integer> list, List<List<Integer>> lists) {
        if (list.size() > 1) {
            lists.add(new ArrayList<>(list));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = pos; i < nums.length; i++) {
            // 与其他回溯题目处理重复情况不同的是，这里使用set。12345111这种情况，因为没有排序，故相同的数字1不在一起，可能重复
            if (set.contains(nums[i]))
                continue;
            set.add(nums[i]);
            if (list.isEmpty() || nums[i] >= list.get(list.size() - 1)) {
                list.add(nums[i]);
                getSubsequences(i + 1, nums, list, lists);
                list.remove(list.size() - 1);
            }
        }
    }

    // 46. 全排列
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        getPermute(nums, new ArrayList<>(), lists, new boolean[nums.length]);
        return lists;
    }

    public void getPermute(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] isVisited) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                list.add(nums[i]);
                getPermute(nums, list, lists, isVisited);
                list.remove(list.size() - 1);
                isVisited[i] = false;
            }
        }
    }

    // 47. 全排列 II
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        // 可以有重复元素，这里排个序，把一样的聚集起来
        Arrays.sort(nums);
        getPermuteUnique(nums, new ArrayList<>(), lists, new boolean[nums.length]);
        return lists;
    }

    public void getPermuteUnique(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] isVisited) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 注意这个条件，这代表了如果前一个数和这个数相同，并且前一个数还没遍历过，就跳过，保证了唯一性
            if (i != 0 && nums[i] == nums[i - 1] && !isVisited[i - 1])
                continue;
            if (!isVisited[i]) {
                isVisited[i] = true;
                list.add(nums[i]);
                getPermuteUnique(nums, list, lists, isVisited);
                list.remove(list.size() - 1);
                isVisited[i] = false;
            }
        }
    }
}
